Draw Towers
Volume Number: 1
Issue Number: 7
Column Tag: STRUCTURED PRogramming in Modula-2
Draw the Towers of Hanoi
By John Bogan
This month we will explore three items. First, we will continue to introduce the
elements of Software Engineering in a historical perspective. Second, we will discuss
why Modula-2 is not a hackers’ language and finally, we will look at a sample program
that uses the Mac ROM to draw the starting position for the Towers of Hanoi.
A New Direction
Last month we saw that Software Engineering is capable of being abused as well as
being able to provide important insights into the process of building good computer
software. By the late 1960’s the Software Engineers had, in effect, dictated that
COBOL would be the primary language of the FORTUNE 1000 probably until the end of
the century. Most microcomputer programmers faced with the prospect of coding in
COBOL would shudder in terror at the thought.
In 1968 Software Engineering took a turn for the better when a famous and well
regarded European computer scientist lit a fire under the COBOL and FORTRAN
programming community, a fire whose embers still smolder and flare up to this day.
The scientist was E.W. Dijkstra and the arson was committed in the Communications of
the ACM with a letter entitled “GOTO Statement Considered Harmful”. In this letter
Dijkstra observed that after having read a multitude of programs in a variety of
languages that the quality of a program was inversely proportional to the number of
GOTO statements in that program. The graph below illustrates this discovery.
The idea is simple ... jumping around a program with branching statements leads
to unreadable program texts (known in the trade as spaghetti code) which are next to
impossible to debug or for a third party to pick up and read. Since ALGOL-60 (the
European’s favorite language) has advanced control structures which permits GOTOless
programming and FORTRAN doesn’t, the battle lines were drawn. Letter after letter
poured into the journals feeding the flames.
Finally in 1972 in an effort to quell the controversy Dijkstra together with Dahl
and Hoare published a book on just how to write high quality programs without using
the dangerous GOTO statement. This book, Structured Programming, estab- lished once
and for all that GOTOs are redundant. Every sequential program- ming task can be
accomplished with a combination of three constructs.
• sequence:
BEGIN ... s1 ... s2 ... s3 ... END
• iteration:
WHILE c1 DO ... s1 ... ENDWHILE
• conditional:
IF c1 THEN s1 ENDIF
If acceptance in the curriculum of the worlds’ Universities’ Computer Science
Departments is a valid measure then Structured Programming is an overwhelming
success. Only those programmers corrupted by traditional BASIC or Assembler still
grasp at the past and argue the merits of the GOTO. Meanwhile the course of Software
Engineering was changed forever. An example of this change is Modula-2. This
language is rich in structured control statements and does not support the GOTO at all.
There are no statement labels in Modula-2 and while it is possible to write poor code
in Modula it is impossible to write spaghetti code.
The structured control statements supported by Modula are the statement
sequence, the WHILE ... DO, the REPEAT ... UNTIL, the FOR ... TO ... BY ... DO, the LOOP
... EXIT, the IF ... THEN ... ELSIF, the CASE ... OF and the WITH ... DO statements.
What is Structured?
In some ways this is a very difficult question to answer. For adherents of the
Structured Techniques the concept of “Structured” is very much like the Bible is to
Jerry Falwell. It is the guiding light, the one true path to paradise, the blessed and
final word on how to think about solving complex logical problems.
A slightly more dispassionate view might produce the following definition of
structured - a philosophy for solving problems which attempts to conserve scarce
resources by arriving at the perfect solution in the fewest attempts by following a
plan.
Why Plan When You Can Hack?
The idea of a plan is very important in understanding the Structured Techniques,
Software Engineering and Modula-2. It also illustrates why Modula-2 is not
particularly well suited for hacking. Most hackers I have known use the technique of
incremental discovery or trial by error. In other words programs just grow from
line 1 until the last bell and whistle is debugged. Assembly language and to a lesser
extent C are well suited for this type of programming. Modula-2 most definitely is
not. As we will see in future columns the quaility of a Modula-2 program is dependent
on the quality of the detailed planning that occurs before the first line of code is
written. In many ways this dependence on upfront planning is a distinct disadvantage
for learning a new and unique system like the Mac. So many of the techniques peculiar
to the Mac (such as the entire user interface or resources or Quickdraw) are best
approached and mastered by trial and error hacks. When you combine this reality
with the compile-link-execute overhead of Modula-2 it should be obvious why
Modula-2 is not particularly suited to casual hacking. A good strategy for making the
best use of Modula-2 would be to learn the Mac with Apple’s interpreted Pascal and
then to translate these programs into the much faster Modula-2. As we progress in
these columns we will see just how close Modula and Pascal are to each other so this
suggestion won’t seem so painful. The bottom line is that Modula-2 is not a language
for the seat-of-the-pants hacker.
This Month’s Code
The piece of Modula-2 code that follows is primarily useful because it shows how
to access the Mac ROM on a 128K machine. The Quickdraw calls used are SetRect,
PaintRect and PaintRoundRect. You should be aware that the method of specifying ROM
calls is different for a 512K box. Also it should be noted that the data types VHSelect,
Point and Rect could have been imported blindly instead of spelled out but then their
internal structures would have been hidden and the topic of information hiding in
Modula-2 is an advanced and complex issue.
MODULE Hanoi;
(* build starting position for Hanoi Towers *)
FROM Terminal IMPORT ClearScreen;
FROM InOut IMPORT WriteString, ReadCard, WriteLn;
(* data structures for Quickdraw calls *)
TYPE
VHSelect = (v,h);
Point = RECORD
CASE INTEGER OF
0: v: INTEGER;
h: INTEGER;
|1: vh: ARRAY VHSelect OF INTEGER;
END; (* CASE *)
END; (* RECORD *)
Rect = RECORD
CASE INTEGER OF
0: top: INTEGER;
left: INTEGER;
bottom: INTEGER;
right: INTEGER;
|1: topLeft: Point;
botRight: Point;
END; (* CASE *)
END; (* RECORD *)
CONST
CX = 355B;
QuickDraw1ModNum = 2; (* absolute module number
of QuickDraw1 *)
VAR
r: Rect; NumDisks: CARDINAL;
PROCEDURE SetRect (VAR r: Rect; left,top,right,bottom: INTEGER);
CODE CX; QuickDraw1ModNum; 51 END SetRect;
PROCEDURE PaintRect (r: Rect);
CODE CX; QuickDraw1ModNum; 62 END PaintRect;
PROCEDURE PaintRoundRect(r: Rect; ovWd, ovHt: INTEGER);
CODE CX; QuickDraw1ModNum; 67 END PaintRoundRect;
PROCEDURE DrawBase;
CONST
BaseLeft = 36;
BaseTop = 261;
BaseRight = 476;
BaseBottom = 270;
BEGIN
SetRect(r,BaseLeft,BaseTop,BaseRight,BaseBottom);
PaintRect(r);
END DrawBase;
PROCEDURE DrawPosts;
CONST
PostTop = 144;
PostBottom = 261;
PostWidth = 6;
HalfPostWidth = PostWidth DIV 2;
PostPosition = 128;
VAR
n, PostLeft, PostRight: INTEGER;
BEGIN
n:=1;
WHILE n <= 3 DO
PostLeft := (PostPosition * n) - HalfPostWidth;
PostRight := PostLeft + PostWidth;
SetRect(r,PostLeft,PostTop,PostRight,PostBottom);
PaintRect(r);
n:= n + 1;
END; (* WHILE *)
END DrawPosts;
PROCEDURE DrawVarDisks(numberofdisks: CARDINAL);
CONST
bigdiskleft = 128 - 60;
bigdisktop = 261 - 12;
bigdiskright = 128 + 60;
bigdiskbottom = 261;
deltalength = 5;
deltadepth = 12;
VAR leftedge, topedge, rightedge, bottomedge: INTEGER;
i: CARDINAL;
BEGIN
IF (numberofdisks > 2) AND (numberofdisks < 10)
THEN
leftedge := bigdiskleft; topedge := bigdisktop;
rightedge := bigdiskright; bottomedge := bigdiskbottom;
SetRect(r,leftedge,topedge,rightedge,bottomedge);
PaintRoundRect(r,40,40);
FOR i := 1 TO numberofdisks - 1 DO
leftedge := leftedge + deltalength;
topedge := topedge - deltadepth;
rightedge := rightedge - deltalength;
bottomedge := bottomedge - deltadepth;
SetRect(r,leftedge,topedge,rightedge,bottomedge);
PaintRoundRect(r,40,40);
END; (* FOR *)
END; (* IF *)
END DrawVarDisks;
PROCEDURE GetInput(VAR NDisks: CARDINAL);
BEGIN
ClearScreen;
WriteString(“Enter number of disks (between 3 to 9)”);
WriteLn;
WriteString(“To quit - enter number out of range”);
ReadCard(NDisks);
ClearScreen;
END GetInput;
PROCEDURE InitGraphics(NumberofDisks: CARDINAL);
BEGIN
DrawBase;
DrawPosts;
DrawVarDisks(NumberofDisks);
END InitGraphics;
PROCEDURE ExecuteTowers;
VAR Delay: CARDINAL;
BEGIN
FOR Delay := 1 TO 30000 DO END; (* FOR *)
END ExecuteTowers;
BEGIN
GetInput(NumDisks);
WHILE (NumDisks >= 3) AND (NumDisks <= 9) DO
InitGraphics(NumDisks);
ExecuteTowers;
GetInput(NumDisks);
END; (* WHILE *)
END Hanoi.
Referenced by (2):